import com.kiwi.nixu.common.LNode;

import java.awt.*;
import java.time.chrono.MinguoChronology;

/**
 * 给定链表L0→L1→L2→…→Ln-1→Ln，
 * 把链表重新排序为L0→Ln→L1→Ln-1→L2→Ln-2→…。
 * 要求：
 * ①在原来链表的基础上进行排序，即不能申请新的结点；
 * ②只能修改结点的next域，不能修改数据域
 */
public class D如何对链表进行重新排序 {
    /**
     * 分析与解答
     * 主要思路为：
     * 1）首先找到链表的中间结点。
     * 2）对链表的后半部分子链表进行逆序。
     * 3）把链表的前半部分子链表与逆序后的后半部分子链表进行合并，
     * 合并的思路为：分别从两个链表各取一个结点进行合并
     */
    public static LNode findMiddleNode(LNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //遍历链表时每次向前走两步
        LNode fast = head;
        LNode slow = head;
        LNode slowPre = head;
        while (fast != null && fast.next != null) {
            slowPre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //把链表断开成两个独立的子链表
        slowPre.next = null;
        return slow;
    }

    /**
     * 方法功能；对不带头结点的单链表翻转
     * 输入参数：head链表头结点
     *
     * @param head
     * @return
     */
    public static LNode reverse(LNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //前驱节点
        LNode pre = head;
        LNode cur = head.next;
        LNode next;
        pre.next = null;

        //使当前遍历到的节点cur指向其前驱节点
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = cur.next;
            cur = next;
        }
        return pre;
    }

    /**
     * 对链表进行排序
     *
     * @param head
     * @return
     */
    public static void reorder(LNode head) {
        if (head == null || head.next == null) {
            return;
        }
        //前半部分链表第一个节点
        LNode cur1 = head.next;
        LNode mid = findMiddleNode(head.next);
        //后半部分链表逆序后的第一个节点
        LNode cur2 = reverse(mid);
        LNode tmp = null;
        //合并两个链表
        while (cur1.next != null) {
            tmp = cur1.next;
            cur1.next = cur2;
            cur1 = tmp;

            tmp = cur2.next;
            cur2.next = cur1;
            cur2 = tmp;
        }
        cur1.next = cur2;
    }


    public static void main(String[] args) {
        int i = 1;
        LNode head = new LNode();
        head.next = null;
        LNode tmp = null;
        LNode cur = head;
        //构造第一个链表
        for (; i < 8; i++) {
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        System.out.print("排序前：");
        for (cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + " ");
        }
        reorder(head);
        System.out.print("\n排序后：");
        for (cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + " ");
        }
    }

    /**
     * 引申：如何查找链表的中间结点分析与解答：
     * 主要思路：
     * 用两个指针从链表的第一个结点开始同时遍历结点，一个快指针每次走两步，另外一个慢指针每次走一步；
     * 当快指针先到链表尾部时，慢指针则恰好到达链表中部（快指针到链表尾部时，
     * 当链表长度为奇数时，慢指针指向的即是链表中间指针，
     * 当链表长度为偶数时，慢指针指向的结点和慢指针指向结点的下一个结点都是链表的中间结点）。
     * 上面的代码FindMiddleNode就是用来求链表的中间结点的。
     */
    private static class 如何查找链表的中间节点 {

    }
}
